/*
 * Copyright (C) 2009,2010,2011  Paulo Cesar Pereira de Andrade.
 *
 * This is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This software is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * Authors:
 *	Paulo Cesar Pereira de Andrade
 */

#include "exl.h"

#define cse_store			1
#define cse_binary			2
#define cse_pre				4

#define value_data_length		(sizeof(eobject_t) * 4)
#define unary_data_length		(sizeof(eobject_t) * 2)
#define binary_data_length		(sizeof(eobject_t) * 3)

/*
 * Prototypes
 */
static void
cse(efunction_t *function);

static void
cse_single_path(elabel_t *label);

static ebool_t
cse_unsafe_p(eobject_t list, empz_t mask);

static elabel_t *
cse_pre_label(efunction_t *function, east_node_t *node, east_node_t **match);

#if DEBUG
static ebool_t
cse_deep_pre_unsafe_p(elabel_t *base, elabel_t *label,
		      esymbol_t *atom, eint32_t bit, eint32_t ssa);

static ebool_t
cse_pre_unsafe_p(efunction_t *function,
		 elabel_t *base, elabel_t *label, east_node_t *node);
#endif

static ebool_t
cse_pre_check(efunction_t *function, eentry_t *entry, ebool_t unary);

static eint32_t
cse_count(efunction_t *function, eentry_t *entry, ebool_t unary);

static void
cse_check(efunction_t *function);

static void
cse_replace(efunction_t *function, eentry_t *entry);

static void
cse_link(efunction_t *function, eint32_t state,
	 east_list_t *base, east_list_t *link, east_list_t *tail);

static evector_t *
cse_set_cache(evector_t **pointer, eint32_t length);

static eobject_t *
cse_get_cache(evector_t *vector, eint32_t length);

static void
cse_unary_hash(elabel_t *label, east_list_t *base, east_list_t *tail,
	       east_node_t *arg0,
	       ecode_t code, ebool_t store);

static void
cse_binary_hash(elabel_t *label, east_list_t *base, east_list_t *tail,
		east_node_t *arg0, east_node_t *arg1,
		ecode_t code, ebool_t store);

static void
cse_hash(ehash_t *hash, evector_t *vector, elabel_t *label,
	 east_list_t *base, east_list_t *tail,
	 eobject_t *data, eint32_t length, ebool_t store);

/*
 * Initialization
 */
static ebool_t		 again;
static ehash_t		*mask_hash;
static ehash_t		*unary_hash;
static ehash_t		*binary_hash;
static eobject_t	*unary_data;
static eobject_t	*binary_data;
static evector_t	*value_cache;
static evector_t	*unary_cache;
static evector_t	*binary_cache;
static evector_t	*cse_root;

/*
 * Implementation
 */
void
init_cse(void)
{
    eobject_t		*root;

    evector(&cse_root, t_void, 8, 1);
    eadd_root((eobject_t *)&cse_root);
    root = cse_root->v.ptr;

    enew_hash((eobject_t *)&mask_hash, H_pointer, 5);
    root[0] = mask_hash;

    enew_hash((eobject_t *)&unary_hash, H_string, 5);
    root[1] = unary_hash;

    enew_hash((eobject_t *)&binary_hash, H_string, 5);
    root[2] = binary_hash;

    enew_object((eobject_t *)&unary_data, t_void, unary_data_length);
    root[3] = unary_data;

    enew_object((eobject_t *)&binary_data, t_void, binary_data_length);
    root[4] = binary_data;

    value_cache = cse_set_cache((evector_t **)(root + 5), value_data_length);

    unary_cache = cse_set_cache((evector_t **)(root + 6), unary_data_length);

    binary_cache = cse_set_cache((evector_t **)(root + 7), binary_data_length);
}

void
finish_cse(void)
{
    erem_root((eobject_t *)&cse_root);
}

ebool_t
ecse(efunction_t *function)
{
    ebool_t		  change;

    v_check(1);
    v_push(null);
    again = false;
    cse(function);
    change = again;
    if (change) {
	do {
	    again = false;
	    cse(function);
	} while (again);
    }
    v_dec();

    /* can keep cache during all iterations as basic blocks are not modified */
    eclr_hash(mask_hash);

    return (change);
}

static void
cse(efunction_t *function)
{
    east_node_t		*arg0;
    east_node_t		*arg1;
    east_list_t		*base;
    eobject_t		*data;
    east_list_t		*list;
    essa_load_t		*load;
    east_node_t		*node;
    east_list_t		*prev;
    elabel_t		*label;
    eint32_t		 state;
    ebool_t		 store;

#define have_none	0
#define have_arg0	1
#define wait_arg1	2
#define have_arg1	4

    base = null;
    label = null;
    store = false;
    state = have_none;
    arg0 = arg1 = null;
    data = function->loads->v.obj;
    list = prev = function->code;
    for (; list; prev = list, list = east_next(list)) {
	node = east_node(list);
	switch (node->code) {
	    case eop_label:			case eop_block:
		label = node->clabel.label;
		state = have_none;
		break;
	    case eop_nil:			case eop_int:
	    case eop_float:			case eop_ll:
	    case eop_ld:			case eop_ldt:
	    case eop_lb:			case eop_lbt:
	    case eop_lc:
		if (state == wait_arg1) {
		    arg1 = node;
		    state = have_arg1;
		}
		else {
		    base  = prev;
		    arg0  = node;
		    store = false;
		    state = have_arg0;
		}
		break;
	    case eop_push:
		if (state == have_arg0 &&
		     node->cstack.flags & code_stack_binarg)
		    state = wait_arg1;
		else
		    state = have_none;
		break;
	    case eop_sb:
		if (state != have_none)
		    store = true;
		/* check for possible folding of cse temporary */
		else if (node->csymbol.symbol->a_expression) {
		    if ((load = data[node->csymbol.bit]) == null ||
			(arg0 = load->data[node->csymbol.ssa].node) == null)
			break;
		    /* use implicit load */
		    state = have_arg0;
		    store = false;
		    base  = prev;
		}
		break;
	    case eop_sd:			case eop_sdt:
	    case eop_sbt:			case eop_ss:
	    case eop_sst:			case eop_ssv:
	    case eop_svai:
		if (state != have_none)
		    store = true;
		break;
	    case eop_bool:			case eop_not:
	    case eop_inc:			case eop_dec:
	    case eop_com:			case eop_inv:
	    case eop_neg:			case eop_signbit:
	    case eop_signum:			case eop_rational:
	    case eop_integer_p:			case eop_rational_p:
	    case eop_float_p:			case eop_real_p:
	    case eop_complex_p:			case eop_number_p:
	    case eop_finite_p:			case eop_inf_p:
	    case eop_nan_p:			case eop_num:
	    case eop_den:			case eop_real:
	    case eop_imag:			case eop_arg:
	    case eop_conj:			case eop_floor:
	    case eop_trunc:			case eop_round:
	    case eop_ceil:			case eop_abs:
	    case eop_sqrt:			case eop_cbrt:
	    case eop_sin:			case eop_cos:
	    case eop_tan:			case eop_asin:
	    case eop_acos:			case eop_atan:
	    case eop_sinh:	    		case eop_cosh:
	    case eop_tanh:			case eop_asinh:
	    case eop_acosh:			case eop_atanh:
	    case eop_proj:			case eop_exp:
	    case eop_log:			case eop_log2:
	    case eop_log10:
		if (state == have_arg0)
		    cse_unary_hash(label, base, list, arg0,
				   node->code, store);
		state = have_none;
		break;
	    case eop_ne:			case eop_lt:
	    case eop_le:			case eop_eq:
	    case eop_ge:			case eop_gt:
	    case eop_and:			case eop_or:
	    case eop_xor:			case eop_mul2:
	    case eop_div2:			case eop_shl:
	    case eop_shr:			case eop_add:
	    case eop_sub:			case eop_mul:
	    case eop_div:			case eop_trunc2:
	    case eop_rem:			case eop_atan2:
	    case eop_pow:			case eop_hypot:
	    case eop_complex:
		if (state == have_arg1)
		    cse_binary_hash(label, base, list, arg0, arg1,
				    node->code, store);
		state = have_none;
		break;
	    case eop_note:
		break;
	    default:
		state = have_none;
		break;
	}
    }

    cse_check(function);
    eclr_hash(unary_hash);
    eclr_hash(binary_hash);
    value_cache->offset = unary_cache->offset = binary_cache->offset = 0;
}

#define zmsk				thr_zr
static void
cse_single_path(elabel_t *label)
{
    elabel_t		**dsts;
    eint32_t		  offset;

    /* only recurse if basic block has a single source */
    if (label->srcs->offset == 1) {

	/* if basic block not yet visited */
	if (mpz_tstbit(zmsk, label->ident))
	    return;
	mpz_setbit(zmsk, label->ident);

	dsts = label->dsts->v.obj;
	for (offset = 0; offset < label->dsts->offset; offset++)
	    cse_single_path(dsts[offset]);
    }
}

static ebool_t
cse_unsafe_p(eobject_t list, empz_t mask)
{
    elabel_t		 *label;
    eobject_t		 *value;

    for (; list; list = ecdr(list)) {
	value = ecar(list);
	label = value[0];
	if (!mpz_tstbit(mask, label->ident))
	    return (true);
    }

    return (false);    
}

static elabel_t *
cse_pre_label(efunction_t *function, east_node_t *node, east_node_t **match)
{
    eobject_t		*data;
    elabel_t		*label;
    essa_store_t	*store;

    switch (node->code) {
	case eop_ld:				case eop_ldt:
	case eop_lb:				case eop_lbt:
	case eop_lc:
	    if (node->csymbol.bit >= function->stores->length)
		return (null);
	    data = function->stores->v.obj;
	    if ((store = data[node->csymbol.bit]) == null)
		return (null);
	    if ((label = store->data[node->csymbol.ssa].label))
		*match = node;
	    return (label);
	default:
	    break;
    }

    return (null);
}

#if DEBUG
static ebool_t
cse_deep_pre_unsafe_p(elabel_t *base, elabel_t *label,
		      esymbol_t *atom, eint32_t bit, eint32_t ssa)
{
    elabel_t		**srcs;
    east_list_t		 *list;
    east_node_t		 *node;
    eint32_t		  offset;

    if (/* reached basic block setting value */
	label == base ||
	/* basic block already visited */
	mpz_tstbit(zmsk, label->ident))
	return (false);
    mpz_setbit(zmsk, label->ident);

    if (mpz_tstbit(label->set, bit))
	/* found an intermediate source that modifies the value */
	return (true);

    if (mpz_tstbit(label->use, bit)) {
	list = east_next(elabel_list(label));
	for (; list; list = east_next(list)) {
	    node = east_node(list);
	    switch (node->code) {
		case eop_label:			case eop_block:
		    /* this should really be an impossible condition */
		    return (true);
		case eop_ld:			case eop_ldt:
		case eop_lb:			case eop_lbt:
		case eop_lc:
		    /* if this happens the symbol can reach this
		     * basic block from multiple path */
		    if (node->csymbol.symbol == atom &&
			node->csymbol.ssa == ssa)
			goto found;
		default:
		    break;
	    }
	}
    found:
	if (list == null)
	    /* another impossible condition */
	    return (true);
    }

    srcs = label->srcs->v.obj;
    for (offset = 0; offset < label->srcs->offset; offset++)
	/* recurse on source basic blocks until base */
	if (cse_deep_pre_unsafe_p(base, srcs[offset],
				  atom, bit, ssa))
	    return (true);

    return (false);
}

static ebool_t
cse_pre_unsafe_p(efunction_t *function,
		 elabel_t *base, elabel_t *label, east_node_t *node)
{
    /*   Check for unexpected conditions where the (P)artial (R)edundancy
     * (E)limination done by moving the (C)ommon (S)ubexpression (E)limination
     * expression to another basic block would cause generation of wrong
     * code.
     */
    mpz_set_ui(zmsk, 0);

    return (cse_deep_pre_unsafe_p(base, label,
				  node->csymbol.symbol,
				  node->csymbol.bit,
				  node->csymbol.ssa));
}
#endif

static ebool_t
cse_pre_check(efunction_t *function, eentry_t *entry, ebool_t unary)
{
    east_list_t		*list;
    east_list_t		*tail;
    east_node_t		*node;
    east_node_t		*lnode;
    east_node_t		*rnode;
    elabel_t		*first;
    elabel_t		*label;
    eobject_t		*value;
    eint32_t		 state;
    elabel_t		*llabel;
    elabel_t		*rlabel;

    /* first label used if there is no assignment to cse variables */
    first = east_node(function->code)->clabel.label;

    value = ecar(entry->value);
    /* label of first ocurrence of expression */
    label = value[0];
    state = eget_fixnum(value[3]);

    value = entry->name;
    lnode = null;
    llabel = cse_pre_label(function, value[0], &lnode);
    if (llabel == label)
	/* cannot lift expression */
	return (false);

    if (llabel == null)
	/* no assigments to left operand or is a constant */
	llabel = first;

    if (!unary) {
	rnode = null;
	rlabel = cse_pre_label(function, value[1], &rnode);
	if (rlabel == label)
	    /* cannot lift expression */
	    return (false);

	if (rlabel == null)
	    /* no assigments to right operand or is a constant */
	    rlabel = first;

	if (rlabel->ident > llabel->ident) {
	    /* if right operand assignment happens after left one if any */
#if DEBUG
	    if (lnode && rnode)
		assert(cse_pre_unsafe_p(function,
					llabel, rlabel, rnode) == false);
#endif
	    llabel = rlabel;
	    lnode = rnode;
	}

#if DEBUG
	else if (llabel->ident > rlabel->ident) {
	    if (lnode && rnode)
		assert(cse_pre_unsafe_p(function,
					rlabel, llabel, lnode) == false);
	}
#endif

	else if (llabel == rlabel) {

	    /* special case of origin of both operands in same basic block */

	    if (lnode == null)
		/* if left operand not assigned */
		lnode = rnode;

	    else if (rnode != null) {
		/* if right operand assigned */

		list = east_next(elabel_list(llabel));
		for (; list; list = east_next(list)) {
		    node = east_node(list);
		    if (node == rnode)
			/* left operand assigned last */
			break;

		    if (node == lnode) {
			/* right operand assigned last */
			lnode = rnode;
			break;
		    }
		}

		assert(list != null);
	    }
	}
    }

    list = east_next(elabel_list(llabel));
    if (lnode) {
	for (; list; list = east_next(list)) {
	    rnode = east_node(list);
	    switch (rnode->code) {
		case eop_sd:			case eop_sdt:
		case eop_sb:			case eop_sbt:
		case eop_sc:
		    if (lnode->csymbol.symbol == rnode->csymbol.symbol &&
			lnode->csymbol.ssa == rnode->csymbol.ssa)
			goto found;
		default:
		    break;
	    }
	}
    }
    /* else list is already pointing to eop_enter */

found:
    assert(list != null);

    /* no longer first entry */
    value = ecar(entry->value);
    tail = value[2];
    value[2] = east_next(tail);

    /* remember need to rematerialize expression in another basic block */
    state |= cse_pre;
    value = cse_get_cache(value_cache, value_data_length);
    value[0] = llabel;
    value[1] = list;
    value[2] = list;
    value[3] = efixnum(state);
    entry->value = econs(value, entry->value);

    return (true);
}

static eint32_t
cse_count(efunction_t *function, eentry_t *entry, ebool_t unary)
{
    elabel_t		**dsts;
    eobject_t		  list;
    empz_t		  mask;
    eobject_t		  prev;
    eint32_t		  count;
    elabel_t		 *label;
    eobject_t		 *value;
    eentry_t		 *mentry;
    eint32_t		  offset;

    prev = entry->value;

    /* if expression not repeated */
    if ((list = ecdr(prev)) == null)
	return (0);

    /* if unary operation and only one cse candidate */
    if (unary && ecdr(list) == null)
	return (0);

    value = ecar(prev);
    label = value[0];

    /* check if safe cse targets of this basic block are cached */
    if ((mentry = eget_hash(mask_hash, label)) == null) {
	mpz_set_ui(zmsk, 0);
	mpz_setbit(zmsk, label->ident);
	dsts = label->dsts->v.obj;
	for (offset = 0; offset < label->dsts->offset; offset++)
	    /* all destinations of this basic block are cse candidates */
	    cse_single_path(dsts[offset]);
	enew(&mentry, entry);
	mentry->name = label;
	eput_hash(mask_hash, mentry);
	enew_mpz(&mentry->value, zmsk);
    }
    mask = mentry->value;

    count = elength(list);
    if (cse_unsafe_p(list, mask)) {
	if (!cse_pre_check(function, entry, unary)) {
	    /* remove unsafe cse replacements */
	    for (; list; prev = list, list = ecdr(list)) {
		value = ecar(list);
		label = value[0];
		if (!mpz_tstbit(mask, label->ident)) {
		    erplacd(prev, ecdr(list));
		    list = prev;
		    --count;
		}
	    }
	}
	else
	    --count;
    }

    return (count);
}
#undef zmsk

static void
cse_check(efunction_t *function)
{
    ehash_t		*hash;
    eentry_t		*entry;
    eint32_t		 offset;

    hash = unary_hash;
    if (hash->count) {
	for (offset = 0; offset < hash->size; offset++) {
	    for (entry = hash->entries[offset]; entry; entry = entry->next) {
		entry->value = ereverse(entry->value);
		/* if more then one extra use of unary expression */
		if (cse_count(function, entry, true) > 1)
		    cse_replace(function, entry);
	    }
	}
    }

    hash = binary_hash;
    if (hash->count) {
	for (offset = 0; offset < hash->size; offset++) {
	    for (entry = hash->entries[offset]; entry; entry = entry->next) {
		entry->value = ereverse(entry->value);
		/* if at least one extra use of binary expression */
		if (cse_count(function, entry, false) >= 1)
		    cse_replace(function, entry);
	    }
	}
    }
}

static void
cse_replace(efunction_t *function, eentry_t *entry)
{
    esymbol_t		*atom;
    east_list_t		*base;
    east_list_t		*link;
    eobject_t		 list;
    east_node_t		*node;
    east_list_t		*tail;
    elabel_t		*label;
    eobject_t		*value;
    eint32_t		 state;

    list  = entry->value;
    value = ecar(list);
    label = value[0];
    tail  = value[2];
    state = eget_fixnum(value[3]);

    atom = enew_temp_symbol(function);

    node = ecode_symbol_store(atom);
    v_top() = node;

    essa_symbol_state(function, label, atom, ssa_set);

    link = east_no_link(node);
    v_top() = link;
    essa_store_symbol(function, label, link);

    /* link store of cse temporary */
    east_next(link) = east_next(tail);
    east_next(tail) = link;

    /* insert store of cse temporary */
    if (state & cse_pre) {
	value = entry->name;

	/* link operation */
	if (state & cse_binary)
	    node = ecode_binary(eget_fixnum(value[2]));
	else
	    node = ecode_unary(eget_fixnum(value[1]));
	v_top() = node;
	link = east_no_link(node);
	east_next(link) = east_next(tail);
	east_next(tail) = link;

	if (state & cse_binary) {
	    /* link righ argument */
	    node = value[1];
	    link = east_no_link(node);
	    east_next(link) = east_next(tail);
	    east_next(tail) = link;

	    /* link push of left argument */
	    node = ecode_push_binarg();
	    v_top() = node;
	    link = east_no_link(node);
	    east_next(link) = east_next(tail);
	    east_next(tail) = link;
	}

	/* link left argument */
	node = value[0];
	link = east_no_link(node);
	east_next(link) = east_next(tail);
	east_next(tail) = link;
    }

    node = ecode_symbol_load(atom);
    v_top() = node;

    /* expand first loop iteration to get shared node pointer */
    list  = ecdr(list);
    value = ecar(list);
    label = value[0];
    base  = value[1];
    tail  = value[2];
    state = eget_fixnum(value[3]);
    essa_symbol_state(function, label, atom, ssa_use);
    link  = east_no_link(node);
    v_top() = link;
    essa_load_symbol(function, label, link);
    node = east_node(link);
    cse_link(function, state, base, link, tail);

    for (list = ecdr(list); list; list = ecdr(list)) {
	value = ecar(list);
	label = value[0];
	base  = value[1];
	tail  = value[2];
	state = eget_fixnum(value[3]);
	essa_symbol_state(function, label, atom, ssa_use);
	link  = east_no_link(node);
	v_top() = link;
	essa_load_symbol(function, label, link);
	cse_link(function, state, base, link, tail);
    }

    again = true;
}

static void
cse_link(efunction_t *function, eint32_t state,
	 east_list_t *base, east_list_t *link, east_list_t *tail)
{
    east_list_t		*list;
    east_node_t		*node;

    switch (state) {
	case 0:
	case cse_binary:
	    for (list = east_next(base); list != tail; list = east_next(list)) {
		node = east_node(list);
		switch (node->code) {
#if 0
		    /* should only match store of cse temporaries, but they
		     * are not replaced here, but in ecfg.c "cleanup" code */
		    case eop_sd:		case eop_sdt:
		    case eop_sb:		case eop_sbt:
		    case eop_sc:
			essa_del_list_set(function, list);
			break;
#endif
		    case eop_ld:		case eop_ldt:
		    case eop_lb:		case eop_lbt:
		    case eop_lc:
			essa_del_list_use(function, list);
			break;
		    default:
			break;
		}
	    }

	    /* insert/replace load of cse temporary */
	    east_next(link) = tail;
	    east_next(base) = link;
	    break;

	case cse_store:
	    for (list = east_next(base);
		 east_next(list) != tail;
		 base = list, list = east_next(list))
		;

#if DEBUG
	    switch (east_node(list)->code) {
		case eop_bool:			case eop_not:
		case eop_inc:			case eop_dec:
		case eop_com:			case eop_inv:
		case eop_neg:			case eop_signbit:
		case eop_signum:		case eop_rational:
		case eop_integer_p:		case eop_rational_p:
		case eop_float_p:		case eop_real_p:
		case eop_complex_p:		case eop_number_p:
		case eop_finite_p:		case eop_inf_p:
		case eop_nan_p:			case eop_num:
		case eop_den:			case eop_real:
		case eop_imag:			case eop_arg:
		case eop_conj:			case eop_floor:
		case eop_trunc:			case eop_round:
		case eop_ceil:			case eop_abs:
		case eop_sqrt:			case eop_cbrt:
		case eop_sin:			case eop_cos:
		case eop_tan:			case eop_asin:
		case eop_acos:			case eop_atan:
		case eop_sinh:			case eop_cosh:
		case eop_tanh:			case eop_asinh:
		case eop_acosh:			case eop_atanh:
		case eop_proj:			case eop_exp:
		case eop_log:			case eop_log2:
		case eop_log10:
		    break;
		default:
		    abort();
	    }
#endif

	    /* insert load of cse temporary */
	    east_next(base) = link;
	    east_next(link) = tail;
	    break;

	case cse_store|cse_binary:
	    for (list = east_next(base);
		 east_next(list) != tail;
		 base = list, list = east_next(list)) {
		/* remove push of left binary operation argument */
		if (east_node(list)->code == eop_push) {
#if DEBUG
		    /* ensure it does not do something wrong */
		    assert(state == (cse_store|cse_binary));
		    state = 0;
#endif
		    east_next(base) = east_next(list);
		    list = base;
		}
	    }

#if DEBUG
	    assert(state == 0);
	    switch (east_node(list)->code) {
		case eop_ne:			case eop_lt:
		case eop_le:			case eop_eq:
		case eop_ge:			case eop_gt:
		case eop_and:			case eop_or:
		case eop_xor:			case eop_mul2:
		case eop_div2:			case eop_shl:
		case eop_shr:			case eop_add:
		case eop_sub:			case eop_mul:
		case eop_div:			case eop_trunc2:
		case eop_rem:			case eop_atan2:
		case eop_pow:			case eop_hypot:
		case eop_complex:
		    break;
		default:
		    abort();
	    }
#endif

	    /* insert load of cse temporary */
	    east_next(base) = link;
	    east_next(link) = tail;
	    break;

	default:
	    abort();
    }
}

static evector_t *
cse_set_cache(evector_t **pointer, eint32_t length)
{
    evector_t		*vector;
    eint32_t		 offset;

    evector(pointer, t_void, 16, 1);
    vector  = *pointer;
    for (offset = 0; offset < 16; offset++)
	enew_object(vector->v.ptr + offset, t_void, length);

    return (vector);
}

static eobject_t *
cse_get_cache(evector_t *vector, eint32_t length)
{
    eobject_t		*value;
    eint32_t		 offset;

    if (vector->offset >= vector->length) {
	erenew_vector(vector, vector->length + 16);
	value = vector->v.ptr;
	for (offset = vector->offset; offset < vector->length; offset++)
	    enew_object(value + offset, t_void, length);
    }
    else
	value = vector->v.ptr;

    return (value[vector->offset++]);
}

static void
cse_unary_hash(elabel_t *label, east_list_t *base, east_list_t *tail,
	       east_node_t *arg0,
	       ecode_t code, ebool_t store)
{
    unary_data[0] = arg0;
    unary_data[1] = efixnum(code);
    cse_hash(unary_hash, unary_cache, label, base, tail,
	     unary_data, unary_data_length, store);
}

static void
cse_binary_hash(elabel_t *label, east_list_t *base, east_list_t *tail,
		east_node_t *arg0, east_node_t *arg1,
		ecode_t code, ebool_t store)
{
    binary_data[0] = arg0;
    binary_data[1] = arg1;
    binary_data[2] = efixnum(code);
    cse_hash(binary_hash, binary_cache, label, base, tail,
	     binary_data, binary_data_length, store);
}

static void
cse_hash(ehash_t *hash, evector_t *vector, elabel_t *label,
	 east_list_t *base, east_list_t *tail,
	 eobject_t *data, eint32_t length, ebool_t store)
{
    eentry_t		*entry;
    eobject_t		*value;
    eint32_t		 state;

    if ((entry = eget_hash(hash, data)) == null) {
	value = cse_get_cache(vector, length);
	enew(&entry, entry);
	v_top() = entry;
	entry->name = value;
	memcpy(entry->name, data, length);
	eput_hash(hash, entry);
    }
    else
	tail = east_next(tail);

    state = store ? cse_store : 0;
    if (length == binary_data_length)
	state |= cse_binary;

    value = cse_get_cache(value_cache, value_data_length);
    value[0] = label;
    value[1] = base;
    value[2] = tail;
    value[3] = efixnum(state);
    entry->value = econs(value, entry->value);
}
